#include <bits/stdc++.h>

using namespace std;

// 完全没有重复的数字个数
// 给定正整数n，返回在[1, n]范围内每一位都互不相同的正整数个数
// 测试链接 : https://leetcode.cn/problems/count-special-integers/

class Solution 
{
public:
    int countSpecialNumbers(int n) 
    {
        int len = 1;
        int offset = 1;
        int tmp = n / 10;
        while(tmp > 0)
        {
            ++len;
            tmp /= 10;
            offset *= 10;
        }    
		// cnt[i] :
		// 一共长度为len，还剩i位没有确定，确定的前缀为len-i位，且确定的前缀不为空
		// 0~9一共10个数字，没有选择的数字剩下10-(len-i)个
		// 那么在后续的i位上，有多少种排列
		// 比如：len = 4
		// cnt[4]不计算
		// cnt[3] = 9 * 8 * 7
		// cnt[2] = 8 * 7
		// cnt[1] = 7
		// cnt[0] = 1，表示前缀已确定，后续也没有了，那么就是1种排列，就是前缀的状况
		// 再比如：len = 6
		// cnt[6]不计算
		// cnt[5] = 9 * 8 * 7 * 6 * 5
		// cnt[4] = 8 * 7 * 6 * 5
		// cnt[3] = 7 * 6 * 5
		// cnt[2] = 6 * 5
		// cnt[1] = 5
		// cnt[0] = 1，表示前缀已确定，后续也没有了，那么就是1种排列，就是前缀的状况
		// 下面for循环就是求解cnt的代码
        int cnt[len];
        cnt[0] = 1;
        for(int i = 1, k = 10 - len + 1; i < len; ++i, ++k)
        {
            cnt[i] = cnt[i - 1] * k;
        }
        int ans = 0;
        if(len >= 2)
        {
			// 如果n的位数是len位，先计算位数少于len的数中，每一位都互不相同的正整数个数，并累加
			// 所有1位数中，每一位都互不相同的正整数个数 = 9
			// 所有2位数中，每一位都互不相同的正整数个数 = 9 * 9
			// 所有3位数中，每一位都互不相同的正整数个数 = 9 * 9 * 8
			// 所有4位数中，每一位都互不相同的正整数个数 = 9 * 9 * 8 * 7
			// ...比len少的位数都累加...
            ans = 9;
            for(int i = 2, s = 9, k = 9; i < len; ++i, --k)
            {
                s *= k;
                ans += s;
            }
        }
		// 如果n的位数是len位，已经计算了位数少于len个的情况
		// 下面计算一定有len位的数字中，<=n且每一位都互不相同的正整数个数
        int first = n / offset;
        // 小于num最高位数字的情况
        ans += (first - 1) * cnt[len - 1];
        // 后续累加上，等于num最高位数字的情况
        ans += f(cnt, n, len - 1, offset / 10, 1 << first);
        return ans;
    }

	// 之前已经确定了和num一样的前缀，且确定的部分一定不为空
	// 还有len位没有确定
	// 哪些数字已经选了，哪些数字没有选，用status表示
	// 返回<=num且每一位数字都不一样的正整数有多少个
    int f(int* cnt, int num, int len, int offset, int status)
    {
        if(len == 0) return 1; // num自己
        int ans = 0;
        // first是num当前位的数字
        int first = (num / offset) % 10;
        for(int cur = 0; cur < first; ++cur)
        {
            if((status & (1 << cur)) == 0)
            {
                ans += cnt[len - 1];
            }
        }
        if((status & (1 << first)) == 0)
        {
            ans += f(cnt, num, len - 1, offset / 10, status | (1 << first));
        }
        return ans;
    }
};


class Solution 
{
public:
    int countSpecialNumbers(int n) 
    {
        auto s = to_string(n);
        int m = s.size(), dp[m][1 << 10];
        memset(dp, -1, sizeof(dp)); // -1 表示没有计算过
        function<int(int, int, bool, bool)> f = [&](int i, int mask, bool is_limit, bool is_num) -> int
        {
            // is_num 为 ture 表示得到了一个合法数字
            if(i == m) return is_num;
            if(!is_limit && is_num && dp[i][mask] != -1) return dp[i][mask];
            int ans = 0;
            // 前面的位都没有填数字，这一位也可以选择不填
            if(!is_num) ans = f(i + 1, mask, false, false);
            // 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）    
            int up = is_limit ? s[i] - '0' : 9;
            // 枚举要填入的数字 d，is_num 为 true，
            // d 从 0 开始，否则，d 从 1 开始
            for(int d = 1 - is_num; d <= up; ++d) 
            {
                // d 不在 mask 中
                if((mask & (1 << d)) == 0)
                {
                    ans += f(i + 1, mask | (1 << d), is_limit && d == up, true);
                }
            }
            if(!is_limit && is_num) dp[i][mask] = ans;
            return ans;
        };

        return f(0, 0, true, false);
    }
};